package com.cyc.basic.msb;

/**
 * @Description: 希尔排序 时间复杂度o(n^1.3) , 空间复杂度o(1)
 * @version 1.0
 * @author cyc
 * @date 2021/10/8 17:02
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {9, 6, 11, 3, 5, 12, 8, 7, 10, 15, 14, 4, 1, 13, 2};
        sort(arr);
        print(arr);
    }


    static void sort(int[] arr) {
        //使用Knuth序列
        int h = 1;
        while (h <= arr.length / 3) {
            h = 3 * h + 1;
        }

        for (int gap = h; gap > 0; gap = (gap - 1) / 3) {
            for (int i = gap; i < arr.length; i++) {
                //第一层循环是为了抽出第i张牌
                for (int j = i; j > gap - 1; j -= gap) {
                    //第二层循环是为了拿第一层循环获取到的值和他前面的值作比较, 如果比前面的值小, 则交换位置
                    if (arr[j] < arr[j - gap]) {
                        swap(arr, j, j - gap);
                    }
                }
            }
        }
    }

    /**
     * 希尔排序
     * @param arr
     */
//    static void sort(int[] arr) {
//        //设定一个间隔, 这里取数组长度的一半, 然后外层每次循环再次去间隔的一半
//        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
//            for (int i = gap; i < arr.length; i++) {
//                //第一层循环是为了抽出第i张牌
//                for (int j = i; j > gap-1; j-=gap) {
//                    //第二层循环是为了拿第一层循环获取到的值和他前面的值作比较, 如果比前面的值小, 则交换位置
//                    if (arr[j] < arr[j - gap]) {
//                        swap(arr, j, j - gap);
//                    }
//                }
//            }
//        }
//    }
    static void swap(int[] arr, int i, int j) {
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

    static void print(int[] arr) {
        for (int k = 0; k < arr.length; k++) {
            System.out.print(arr[k] + " ");
        }
        System.out.println();
    }
}
